Methods of converting image data into multi-level image data include error diffusion. Error diffusion is used to convert image data into, for example, binary image data.
In error diffusion, while an error generated by performing multi-level conversion on a certain pixel is being distributed to its neighboring pixels to be subjected to multi-level conversion, multi-level conversion is sequentially performed on pixels generally in the main scanning direction. Accordingly, errors diffused from pixels that have been subjected to multi-level conversion (hereinafter, also referred to as “processed pixels”) are added to the original pixel value of a certain pixel and multi-level conversion is performed on the pixel having the resultant pixel value. There are various error diffusion methods, e.g., the Floyd-Steinberg method and the Burkes method, classified according to an error diffusion pattern.
In the Floyd-Steinberg method, as illustrated in FIG. 8, diffused errors are added to the original pixel value of a pixel 101 such that an error of the first previous pixel in the main scanning direction, an error of a pixel in the same position in the main scanning direction on the first previous line, and errors of pixels before and after the pixel in the same position on the first previous line, namely, the errors of the four pixels in total are added to the pixel value of the pixel. According to the Burkes method, as shown in FIG. 9, diffused errors are added to the original pixel value of the pixel 101 such that errors of the first and second previous pixels in the main scanning direction, an error of a pixel in the same position in the main scanning direction on the first previous line, errors of two pixels before the pixel in the same position on the first previous line, and errors of two pixels after the pixel in the same position on the first previous line, namely, the errors of the seven pixels in total are added to the pixel value of the pixel.
In a case where such image processing is performed by a dedicated circuit, such as an application specific integrated circuit (ASIC), image data is typically stored in a main memory. A line memory holding errors of one line for multi-level conversion is provided in the dedicated circuit. Multi-level conversion is performed on a line-by-line basis. In other words, errors obtained by performing multi-level conversion on a certain line are held by the line memory, errors to be diffused to pixels are calculated on the basis of the errors stored in the line memory upon multi-level conversion on the next line, and the pixels are subjected to multi-level conversion using the diffused errors.
FIGS. 10A and 10B are diagrams each illustrating an order for multi-level conversion in an image. FIG. 10A illustrates the order in which multi-level conversion is implemented in the main scanning direction on a line-by-line basis. The conversion in this case requires a line memory having a size proportional to the number of pixels in the main scanning direction of image data. In FIG. 10B, multi-level conversion using the Floyd-Steinberg method is performed in a direction of 45 degrees on a band-by-band basis. The conversion in this case needs a line memory having a size proportional to the number of pixels in the height of each band.
In the case of FIG. 10A, therefore, the size of the necessary line memory is large. A memory element used in the line memory of the dedicated circuit, such as the ASIC, is more expensive than that in the main memory. Therefore, the cost of such an apparatus requiring a large line memory is increased. On the other hand, in the case of FIG. 10B, since the line memory sized according to the height of each band can be used, the cost of the apparatus is lowered.
FIGS. 11A and 11B are diagrams each illustrating a pixel whose error has to be newly read from a memory for multi-level conversion on a next pixel. Referring to FIG. 11A, assuming that processing is performed in the order of FIG. 10A, when multi-level conversion is performed on a pixel 111 next to the pixel 101, an error value of one pixel 112 has to be newly read from the memory. As for error values of other pixels, the error values used for multi-level conversion on the pixel 101 can be used. Referring to FIG. 11B, assuming that the processing is performed in the order of FIG. 10B, when multi-level conversion is performed on the pixel 111 next to the pixel 101, error values of two pixels 112 have to be read from the memory. As for error values of other pixels, the error values used for multi-level conversion on the pixel 101 can be used.
As described above, performing multi-level conversion in the order of FIG. 10B increases the number of accesses to the memory. This causes a reduction in the rate of multi-level conversion. In the multi-level conversion in the order shown in FIG. 10B, therefore, the rate of multi-level conversion is reduced, though the line memory may have a small size.
Such a problem may occur in general image processing in which a value of each pixel in an image is obtained in a predetermined order using calculation results for its neighboring pixels that have been processed.